from  deslab import *
from networkx import relabel_nodes
"""
This is the script for the computation of minimal event bases that ensure diagnosability.
The algorithms are part of the paper:
Basilio, J., Lima, S., Lafortune, S.,, e Moreira, M. (2012), "Computation of minimal
event bases that ensure diagnosability," Discrete Event Dynamic Systems,
 
"""
from itertools import product as cart_product
from collections import OrderedDict, namedtuple
set = frozenset

def prodcollection(A):
    """ This function calculates the product of collections which
    are contained in the list (or frozenset) of events.
    """      
    # We don't standarsize the stratification of sets   
    # because it is dangerous  
    if A == set([set()]):
        return A    
    B = []
    for ai in A:
        try:
            ai_in = iter(ai).next()  
            ai_in_in = iter(ai_in).next()            
            if isinstance(ai_in, set) :
                if isinstance(iter(ai_in_in).next(), str):
                    B.append(ai)  
                else:
                    raise invalidArgument, 'element %s of collection has more than 2 stratifications'%ai                                                         
            else:
                raise invalidArgument, 'element %s of collection does not have 2 stratifications'%ai   
        except  StopIteration:   
            if ai_in == set():
                continue
            else:   
                raise invalidArgument, 'element %s of collection is empty and it does not have 2 stratifications'%ai                  
            
    # we calculate the product of collections
    list_union = []
    # every p is a tuple with every set
    if B:
        for p in cart_product(*B): 
            # we collapse to the union of elements in the tuple
            p_union = reduce(lambda x, y: x | y, p)
            # we generate the list of these tuples        
            list_union.append(p_union)
            # we form a single set with every element
        collection = set(list_union)   
         
    else:
        collection = set([set()])        
    return collection


def YN_type(xd):
    if all(l=='Y' for x,l in xd):
        return 'Y'
    elif all(l=='N' for x,l in xd):
        return 'N'        
    else:
        return 'YN'
   
    



def minimals_of_poset(poset):
    """This function finds the minimal elements of the 
    poset passed as argument"""
    T = frozenset()
    for x in iter(poset):
        if any (x>a for a in T):
            continue
        else:
            A = frozenset([a for a in T if a > x])
            T = frozenset([x]) | (T - A)
    return T




def find_indeterminate_states(G, Gd, sf):   
    """This function looks for indeterminate states, i. e.
    states that belong to indeterminate  SCCs    
     """
    # Calculating the labeling plant          
    A=labelfailaut(sf) # $A_l$
    Gl = G//A  # G_l
    # Calculating the Gt  
    Gt= Gd//Gl   
    SCC = strconncomps(Gt)      
    SCC_selfloop = [[l] for l in selfloopnodes(Gt)]
    SCC_multiple = [C for C in SCC if (len(C)>1)]
    SCC_nontrivial = SCC_selfloop + SCC_multiple
    CC = set()
    for C in SCC_nontrivial:
        if any(l=='Y' and YN_type(xd)=='YN'  for xd, (x,l) in C):
            CC = CC | set([xd for xd, xn in C])           
    return CC

def proj(s, Sobs):
    """Calculates the projection of the input string S, 
    with respect to observable set Sobs"""
    ps = [e for e in s if e in Sobs]
    return tuple(ps)


def prefixes(s):    
    pref_s = []
    for i in xrange(1,len(s)+1):        
        pref_s.append(s[0:i])  
    return set(pref_s)



def stratify_sigma(Sigma_i):
    if Sigma_i==set():
        return set(set([]))
    
    if len(Sigma_i) == 1:
        if Sigma_i ==  set([set()]):
            return  set()
        else:
            return set([set(e) for e in iter(Sigma_i).next()])
    else:
        # perform stratification
        try:
            s_in = iter(Sigma_i).next()
            s_in_in = iter(s_in).next()
            if isinstance(s_in, set) and isinstance(s_in_in,str):
                S = []
                for E in Sigma_i:
                    P = set([set([e]) for e in E])  
                    S.append(P)                                   
                return prodcollection(S)
        except StopIteration:
            raise invalidArgument, 'element %s has unexpected  stratification'%Sigma_i                  

            

""" New functions for tree calculation"""


def find_FPES(Gd,xd):    
    """ Third function builds the tree for Gd for the
    calculation of Gd in algorithm 1    
    Use drawgraph(tree,'FPES') for drawing the generated trees     """
    
    tree = nx.DiGraph()      
    s = []      
    events = sorted(list(Gd.Gamma(xd)))                
    events_Y = [e for e in events if YN_type(Gd.delta(xd,e))=='Y']    
    stack = [(xd, s, iter(events_Y))]  
    curr_path = [xd]
    FPES = []        
     
    while stack:
        x, s, event_iter = stack[-1]
        try:      
            e = next(event_iter)
            x_n = Gd.delta(x,e)   
            s_n = s+[e]                 
            tree.add_edge((x,tuple(s)) ,(x_n,tuple(s_n)))                                      
            if x_n not in curr_path:  
                curr_path.append(x_n) 
                events_n = sorted(Gd.Gamma(x_n))                                                    
                stack.append((x_n, s_n, iter(events_n)))   
            else:
                S = set([set([h]) for h in s_n])
                FPES.append(S)              
        except StopIteration:
            stack.pop()   
            curr_path.pop() 
    return set(FPES), tree
              



def find_XDS(G):   
    """Generates the set of tuples of prime paths for automaton
    G. The tuples are of the form (x, s) where x is the state,
    s is the string that labels each prime path. It also generates
    the tree of prime paths for testing an academic purposes
    
    Use drawgraph(tree,'XDS') for plotting the tree """ 

    tree = nx.DiGraph() # creation of  tree is merely for academic purpose
    Lf = namedtuple('Lf',['x_d', 's'])   
    x0 = G._X0()     
    s = []      
    events = sorted(list(G.Gamma(x0))) 
    stack = [(x0, s, iter(events))] 
    curr_path = [x0] 
    X_DS = []    
    
    while stack:
        x, s, event_iter = stack[-1]
        try:      
            e = next(event_iter)
            x_n = G.delta(x,e)   
            s_n = s+[e] 
            # create a tree for academic purpose          
            tree.add_edge((x,tuple(s)), (x_n,tuple(s_n)))                                                          
            if x_n not in curr_path:  
                # we dont find a cycle, then advance in current path
                curr_path.append(x_n) 
                events_n = sorted(G.Gamma(x_n))                                       
                stack.append((x_n, s_n, iter(events_n)))   
            else:
                # we find a cycle then add it to set X_DS                            
                X_DS.append(Lf(x_n, tuple(s_n)))                           
        except StopIteration:
            # the events of iterator are exhausted
            stack.pop()   
            curr_path.pop() 
    return X_DS, tree



def prime_paths_cycle_smax(G):   
    """generates the tree of  prime paths for an automaton
    the leafs contain a tuple of the form
    (x, s, c, sm) where x is the state, s is the string
    c is the cycle of the prime path and sm is the maximum
    sequence before a Y cycle
          
    Use drawgraph(tree,'XST') for plotting
    """  
    tree = nx.DiGraph() #  tree is merely for academic purpose
    x0 = G._X0()     
    s = []      
    events = sorted(list(G.Gamma(x0))) 
    stack = [(x0, s, iter(events))] 
    path = OrderedDict([(x0,s)])
    # next object defines the form of the tuple in XST
    Lt = namedtuple('Lt',['xp_d', 'x_d','s','cycle','s_max'])
    XST = []    
    
    while stack:
        x, s, event_iter = stack[-1]
        try:      
            e = next(event_iter)
            x_n = G.delta(x,e)   
            s_n = s+[e] 
            # next 3 lines create a tree for academic purpose              
            tree.add_edge((x,tuple(s)), (x_n,tuple(s_n)))
            # we determine if the new state forms a cycle                                             
            if x_n not in path:  
                # we don't find a cycle, then advance in current path
                path[x_n] = tuple(s_n) 
                events_n = sorted(G.Gamma(x_n))                                       
                stack.append((x_n, s_n, iter(events_n)))   
            else:
                # we find the cycle, then  add it to element of set XST                                
                cycle = s_n[len( path[x_n]): len(s_n)]  
                # we find the s_max string and add it to element of set XST                                                                  
                x_yn = next((xt for xt in reversed(path.keys()) if YN_type(xt[1])=='YN'),())
                if x_yn:                                                 
                    XST.append(Lt(x_n[0], x_n[1], tuple(s_n), tuple(cycle), tuple(path[x_yn])))  
                    # we update the tree only for academic purpose  
                    tree = relabel_nodes(tree, {(x_n, tuple(s_n)): (x_n, tuple(s_n), tuple(cycle), tuple(path[x_yn]))})                          
               
                else:
                    XST.append(Lt(x_n[0], x_n[1], tuple(s_n), tuple(cycle), x_yn)) 
                    # we update the tree only for academic purpose     
                    tree = relabel_nodes(tree, {(x_n, tuple(s_n)): (x_n, tuple(s_n), tuple(cycle), tuple(x_yn))})  
                                  
        except StopIteration:
            # the events of iterator are exhausted
            stack.pop() 
            # the current path has changed
            path.popitem() 
    return XST, tree


def prime_paths_cycle(G):   
    """generates the tree of  prime paths for an automaton
    the leafs contain a tuple of the form
    (x, s, c, sm) where x is the state, s is the string
    c is the cycle of the prime path and sm is the maximum
    sequence before a Y cycle
          
    Use drawgraph(tree,'XST') for plotting
    """  
    tree = nx.DiGraph() #  tree is merely for academic purpose
    x0 = G._X0()     
    s = []      
    events = sorted(list(G.Gamma(x0))) 
    stack = [(x0, s, iter(events))] 
    path = OrderedDict([(x0,s)])
    # next object defines the form of the tuple in XST
    Lt = namedtuple('Lt',['x', 's','cycle'])
    XST = []    
    
    while stack:
        x, s, event_iter = stack[-1]
        try:      
            e = next(event_iter)
            x_n = G.delta(x,e)   
            s_n = s+[e] 
            # next 3 lines create a tree for academic purpose              
            tree.add_edge((x,tuple(s)), (x_n,tuple(s_n)))
            # we determine if the new state forms a cycle                                             
            if x_n not in path:  
                # we don't find a cycle, then advance in current path
                path[x_n] = tuple(s_n) 
                events_n = sorted(G.Gamma(x_n))                                       
                stack.append((x_n, s_n, iter(events_n)))   
            else:
                # we find the cycle, then  add it to element of set XST                                
                cycle = s_n[len( path[x_n]): len(s_n)]  
                # we find the s_max string and add it to element of set XST                                    

                XST.append(Lt(x_n, tuple(s_n), tuple(cycle))) 
                # we update the tree only for academic purpose     
                tree = relabel_nodes(tree, {(x_n, tuple(s_n)): (x_n, tuple(s_n), tuple(cycle))})  
                                  
        except StopIteration:
            # the events of iterator are exhausted
            stack.pop() 
            # the current path has changed
            path.popitem() 
    return XST, tree






